package com.wtgroup.demo.draft;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;
import junit.framework.TestCase;

import java.util.Arrays;

public class SortDraft extends TestCase {

    public void test() {
        Judger.of(() -> {
            int[] nums = RandomUtil.randomArray((int) (Math.random() * 1000 + 1), 0, 100);
            // int[] nums = {2, 9, 11, 17, 24};
            int[] copy1 = Arrays.copyOf(nums, nums.length);
            heapSort(copy1);

            int[] copy2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy2);

            if (!Tools.equals(copy1, copy2)) {
                Tools.printArray(nums);
                Tools.printArray(copy1);
                Tools.printArray(copy2);
                return false;
            }
            return true;
        }).setIterCount(1000).start().print();
    }

    public void testQuickSort() {
        Judger.of(() -> {
            int[] nums = RandomUtil.randomArray((int) (Math.random() * 1000 + 1), 0, 100);
            // int[] nums = {2, 9, 11, 17, 24};
            int[] copy1 = Arrays.copyOf(nums, nums.length);
            SortDraft.quickSort1(copy1);

            int[] copy2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy2);

            if (!Tools.equals(copy1, copy2)) {
                Tools.printArray(nums);
                Tools.printArray(copy1);
                Tools.printArray(copy2);
                return false;
            }
            return true;
        }).setIterCount(1000).start().print();
    }

    public void testMerge() {
        Judger.of(() -> {
            int[] nums = RandomUtil.randomArray((int) (Math.random() * 1000 + 1), 0, 100);
            // int[] nums = {2, 9, 11, 17, 24};
            int[] copy1 = Arrays.copyOf(nums, nums.length);
            new SortDraft().mergeSort(copy1);

            int[] copy2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy2);

            if (!Tools.equals(copy1, copy2)) {
                Tools.printArray(nums);
                Tools.printArray(copy1);
                Tools.printArray(copy2);
                return false;
            }
            return true;
        }).setIterCount(1000).start().print();

    }

    public void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 两种合并思路
        // 中间数组. M2.1 左右先复制出来, 比较回填; M2.2 比较备份到临时数组, 完事了回填

        merge(arr, left, right);

    }

    private void merge(int[] arr, int left, int right) {
        // 复制出左右两个局部有序数组
        int mid = (left + right) / 2;
        int[] leftPrt = new int[mid - left + 1];
        int[] rightPrt = new int[right - mid];
        for (int i = 0, j = left; i < leftPrt.length; ) {
            leftPrt[i++] = arr[j++];
        }
        for (int i = 0, j = mid + 1; i < rightPrt.length; ) {
            rightPrt[i++] = arr[j++];
        }

        // 比较, 回填

        int l = 0, r = 0, arrix = left;
        while (l < leftPrt.length && r < rightPrt.length) {
            if (leftPrt[l] <= rightPrt[r]) {
                arr[arrix++] = leftPrt[l++];
            } else {
                arr[arrix++] = rightPrt[r++];
            }
        }
        while (l < leftPrt.length) {
            arr[arrix++] = leftPrt[l++];
        }
        while (r < rightPrt.length) {
            arr[arrix++] = rightPrt[r++];
        }
    }

    private static void merge_bak(int[] arr, int left, int right, int mid) {
        int[] temp = new int[right - left + 1];
        int m = left, n = mid + 1;
        int tempi = 0;
        for (tempi = 0; tempi < temp.length && m <= mid && n <= right; tempi++) {
            if (arr[m] <= arr[n]) {
                temp[tempi] = arr[m];
                m++;
            } else {
                temp[tempi] = arr[n];
                n++;
            }
        }

        if (n > right) {
            for (int i = tempi; i < temp.length; i++) {
                temp[i] = arr[m++];
            }
        } else {
            for (int i = tempi; i < temp.length; i++) {
                temp[i] = arr[n++];
            }
        }

        for (int i = left, j = 0; i <= right; i++) {
            arr[i] = temp[j++];
        }
    }


    public void shellSort(int[] arr) {
        int N = arr.length;
        for (int gap = N / 2; gap > 0; gap /= 2) {
            for (int i = 1; i < N; i += gap) {
                int curr = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > curr) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = curr;
            }
        }
    }

    public void insertSort(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N - 1; i++) {
            // 当前抓到的牌
            int curr = arr[i + 1];
            int j;
            for (j = i; j >= 0; j--) {
                if (curr < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = curr;
        }
    }

    public void insertSort_bak(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N - 1; i++) {
            // 0~i 有序区; i+1 待插入牌
            int k = arr[i + 1];
            int j = 0;
            for (j = 0; j <= i; j++) {
                if (k >= arr[j]) {
                    continue;
                }
                break;
            }
            // j~i 依次往后移动一位
            for (int l = i; l >= j; l--) {
                Tools.swap(arr, l, l + 1);
            }
        }
    }

    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    Tools.swap(arr, j, j + 1);
                }
            }
        }
    }

    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int mini = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[mini]) {
                    mini = j;
                }
            }
            int t = arr[i];
            arr[i] = arr[mini];
            arr[mini] = t;
        }
    }


    static void quickSort1(int[] arr) {
        func(arr, 0, arr.length - 1);
    }

    static void func(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = arr[left];
        int slot = left+1;
        for (int i = slot; i <= right; i++) {
            if (arr[i] < pivot) {
                Tools.swap(arr, i, slot);
                slot++;
            }
        }

        Tools.swap(arr, left, slot-1);
        func(arr, left, slot - 2);
        func(arr, slot, right);
    }



    static void heapSort(int[] arr) {
        int N = arr.length;
        // 建堆, 大根
        // 从下往上, 堆化
        for (int i = N/2-1; i >=0; i--) {
            siftDown(arr, N, i);
        }

        // 不断弹出堆顶, 整理, 缩小堆范围, 直到0, 数组就有序了
        for (int size = N; size > 0; size--) {
            Tools.swap(arr, 0, size-1);
            siftDown(arr, size - 1, 0);
        }
    }

    private static void siftDown(int[] arr, int size, int curr) {
        int currCopy = arr[curr];
        int childIx;
        while ((childIx = 2 * curr + 1) < size) {
            if (childIx +1 < size && arr[childIx + 1] > arr[childIx]) {
                childIx = childIx + 1;
            }
            if (currCopy > arr[childIx]) {
                break;
            }

            arr[curr] = arr[childIx];
            curr = childIx;
        }

        arr[curr] = currCopy;
    }


}
